package 贪心算法;

public class 通配符匹配 {

    //动态规划
    public static boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for (int i = 1; i < n + 1; i++) {
            if (p.charAt(i-1) == '*'){
                dp[0][i] = true;
            }else {
                break;
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char c = p.charAt(j-1);
                char c1 = s.charAt(i-1);
                if (c == '?' || c==c1){
                    dp[i][j] = dp[i-1][j-1];
                }else if (c == '*'){
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }

    //贪心
    public static boolean isMatch1(String s,String p){
        int sr = s.length();
        int pr = p.length();
        //得到p右起第一个*的位置
        while (sr > 0 && pr > 0 && p.charAt(pr -1) != '*'){
            if (charMatch(s.charAt(sr-1),p.charAt(pr-1))){
                sr--;
                pr--;
            }else {
                return false;
            }
        }
        if (pr == 0){
            return sr==0;
        }
        int si = 0,pi = 0,sre = -1,pre = -1;
        while (si < sr && pi < pr){
            if (p.charAt(pi)=='*'){
                pi++;
                pre = pi;
                sre = si;
            }else if (charMatch(s.charAt(si),p.charAt(pi))){
                si++;
                pi++;
            }else if (sre != -1 && sre + 1< sr){
                sre ++;
                pi = pre;
                si = sre;
            }else {
                return false;
            }
        }

        return allStar(p,pi,pr-1);

    }

    private static boolean allStar(String p,int start,int end){
        for (int i = start; i <= end; i++) {
            if (p.charAt(i) != '*'){
                return false;
            }
        }
        return true;
    }

    private static boolean charMatch(char a,char b){
        return b == '?' || a==b;
    }

    public static void main(String[] args) {
        String s = "hello";
        String p = "*o*";
        System.out.println(isMatch1(s,p));
    }
}
